package _binary_tree

import ListNode
import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printInorder

/**
 *
 * https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/description/?envType=problem-list-v2&envId=binary-tree
 *
 * # 109. 有序链表转换二叉搜索树
 *
 * 给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树。
 *
 *
 * ## 示例 1：[linked](https://assets.leetcode.com/uploads/2020/08/17/linked.jpg)
 *
 * 输入：nums = [-10,-3,0,5,9]
 *
 * 输出：[0,-3,9,-10,null,5]
 *
 * ## 示例 2
 *
 * 输入: head = []
 *
 * 输出: []
 */
class leetcode_109 {
    @Test
    fun test_1() {
        val list = listOf<Int>(-10, -3, 0, 5, 9)
        var header: ListNode? = null
        var p: ListNode? = null
        for (i in 0 until list.size) {
            if (header == null) {
                header = ListNode(list[i])
                p = header
            } else {
                p?.next = ListNode(list[i])
                p = p?.next
            }
        }
        val actual = sortedListToBST(header)

        val n0 = TreeNode(0)
        val n_3 = TreeNode(-3)
        val n_10 = TreeNode(-10)
        val n9 = TreeNode(9)
        val n5 = TreeNode(5)
        val root = n0
        n0.left = n_3
        n0.right = n9
        n_3.left = n_10
        n9.left = n5
        val expect = root
        Assert.assertEquals(printInorder(expect).toString(), printInorder(actual).toString())
    }

    @Test
    fun test_2() {
        val actual = sortedListToBST(null)
        val expect = null
        Assert.assertEquals(expect, actual)
    }

    private fun sortedListToBST(head: ListNode?): TreeNode? {
        /**
        思路：
        1 把链表转成list。
        2 把list转成二叉搜索树

        T - O(N) - 2N
        S - O(N) - 2N
         */
        // 1 终止条件
        if (head == null) {
            return null
        }
        // 2 链表转为List
        var list: ArrayList<Int> = ArrayList()
        var p: ListNode? = head
        while (p != null) {
            list.add(p.`val`)
            p = p.next
        }
        return sortedListToBST(list, 0, list.size - 1)
    }

    private fun sortedListToBST(list: List<Int>, left: Int, right: Int): TreeNode? {
        // 1 终止条件: left > right
        if (list.size == 0) {
            return null
        }
        if (list.size == 1) {
            val node: TreeNode = TreeNode(list[0])
            return node
        }

        if (left > right) {
            return null
        }

        // 3 找出中间节点
        val mid = left + (right - left) / 2
        val node: TreeNode = TreeNode(list[mid])

        // 4 分割左区间
        // 5 分割右区间
        // 6 递归遍历
        node.left = sortedListToBST(list, left, mid - 1)
        node.right = sortedListToBST(list, mid + 1, right)
        return node
    }
}